class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(),wordList.end());
        unordered_set<string> visited;
        queue<pair<string,int> > q;
        q.emplace(beginWord,1);
        
        auto get = [&](string& word){
            vector<string> path;
            for(string& s : wordList){
                int cnt = 0;
                for(int i = 0;i < s.size();i++){
                    if(s[i] != word[i]){
                        cnt++;
                    }
                    if(cnt == 2){
                        break;
                    }
                }
                if(cnt == 1){
                    path.push_back(s);
                }
            }
            return path;
        };
        
        while(!q.empty()){
            auto [word,step] = q.front();
            q.pop();
            
            vector<string> path = get(word);
            for(string& s : path){
                if(!visited.count(s)){
                    if(s == endWord){
                        return step+1;
                    }
                    q.emplace(s,step+1);
                    visited.insert(s);
                }
            }
        }
        return 0;
    }
};
